W7. Combinatorics, Counting Principles, Permutations, Combinations

Author

Zakhar Podyakov

Published

October 16, 2025

Quiz | Flashcards

1. Summary

1.1 Basic Counting Principles
1.1.1 The Sum Rule

The Sum Rule is a fundamental principle used to count the total number of outcomes for two or more mutually exclusive events. Mutually exclusive means that the events cannot happen at the same time; if one occurs, the others cannot.

The rule states that if an event \(E_1\) can occur in \(n_1\) ways, and a second event \(E_2\) can occur in \(n_2\) ways, and the two events are mutually exclusive, then the total number of ways for either \(E_1\) or \(E_2\) to occur is the sum of their individual possibilities: \(n_1 + n_2\).

In set theory, if \(A_1\) is the set of outcomes for the first event and \(A_2\) is the set for the second, their mutual exclusivity means their intersection is empty (\(A_1 \cap A_2 = \emptyset\)). The total number of outcomes is the size of their union: \(|A_1 \cup A_2| = |A_1| + |A_2|\).

Analogy: Imagine a cafe that offers 3 types of coffee and 4 types of tea. A customer can choose a coffee OR a tea, but not both at once. The total number of drink choices is \(3 + 4 = 7\).

1.1.2 The Product Rule

The Product Rule is used when a procedure or task is composed of a sequence of independent steps. It calculates the total number of ways to perform the entire procedure by multiplying the number of ways to perform each step.

If a task can be broken down into two steps, where the first step can be done in \(n_1\) ways and the second step can be done in \(n_2\) ways regardless of the outcome of the first step, then the entire task can be performed in \(n_1 \times n_2\) ways.

In set theory, this corresponds to the Cartesian product of the outcome sets. The total number of ordered pairs is \(|A_1 \times A_2| = |A_1| \cdot |A_2|\).

Analogy: Consider the same cafe, which offers 3 types of coffee and 3 different sizes (Small, Medium, Large). To choose a coffee, a customer must complete two steps: pick a type AND pick a size. The total number of different coffee orders is \(3 \times 3 = 9\).

1.2 Arrangements and Pairs

In combinatorics, we often deal with selecting items from a set. The way we count these selections depends heavily on whether the order of selection matters.

  • An unordered pair is a selection of two items where the order is irrelevant. It is denoted with curly braces, e.g., {x, y}. For example, if you choose two friends, Alice and Bob, for a committee, the pair {Alice, Bob} is the same as {Bob, Alice}.
  • An ordered pair is a selection of two items where the order is significant. It is denoted with parentheses, e.g., (x, y). Here, (x, y) is different from (y, x). For instance, if you are awarding gold and silver medals, the outcome (Alice wins gold, Bob wins silver) is different from (Bob wins gold, Alice wins silver).

This concept extends from pairs to larger selections, known as arrangements or tuples.

1.3 A Framework for Counting

Most counting problems can be categorized by answering two fundamental questions:

  1. Does the order of selection matter?
  2. Are repetitions of items allowed?

This creates a 2x2 framework that guides us to the correct counting technique.

Without Repetitions With Repetitions
Order Matters Permutation: \(P(n, k)\) n-tuple with Repetition: \(n^k\)
Order Doesn’t Matter Combination: \(C(n, k)\) Combination with Repetition: \(\binom{n+k-1}{k}\)

Here, \(n\) is the number of distinct items to choose from, and \(k\) is the number of items being selected.

1.4 Ordered Arrangements (Permutations)
1.4.1 With Repetitions Allowed

This is the most straightforward case. When we are selecting \(k\) items from a set of \(n\) items, order matters, and we can choose the same item more than once. For each of the \(k\) positions in our arrangement, we have \(n\) choices.

By the product rule, the total number of possible arrangements is: \[ n \times n \times \dots \times n \text{ (k times)} = n^k \]

Example: How many 3-digit PINs can be formed using digits 0-9? Here, \(n=10\) and \(k=3\). The answer is \(10^3 = 1000\).

1.4.2 Without Repetitions Allowed (k-Permutations)

A k-permutation is an ordered arrangement of \(k\) distinct elements chosen from a set of \(n\) distinct elements (where \(k \le n\)).

The logic is as follows:

  • For the first position, there are \(n\) choices.
  • For the second, there are \(n-1\) choices left.
  • This continues until the k-th position, for which there are \(n-k+1\) choices.

Using the product rule, the formula for the number of k-permutations is: \[ P(n, k) = n(n-1)(n-2)\dots(n-k+1) \] This can be expressed more concisely using factorials: \[ P(n, k) = \frac{n!}{(n-k)!} \] A permutation of an entire set occurs when \(k=n\). The number of ways to order n distinct items is \(P(n, n) = n!\).

1.5 Unordered Arrangements (Combinations)
1.5.1 Without Repetitions Allowed (k-Combinations)

A k-combination is an unordered selection (a subset) of \(k\) distinct elements from a set of \(n\) distinct elements. Since order does not matter, we are only concerned with which elements are chosen, not the sequence in which they were picked.

We can derive the formula for combinations from the permutation formula. We know that any set of k elements can be arranged in \(k!\) different orders (permutations). The permutation formula \(P(n, k)\) counts all these ordered arrangements. To get the number of unordered sets, we must divide by \(k!\) to remove the distinction of order.

The number of k-combinations, read as “n choose k”, is given by the formula: \[ C(n, k) = \binom{n}{k} = \frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!} \]

1.5.2 With Repetitions Allowed (Stars and Bars)

This technique is used for counting unordered selections where items can be repeated. The problem is often framed as selecting \(k\) items from \(n\) categories.

The Stars and Bars method provides a visual analogy. Imagine we have \(k\) items to choose (the “stars,” *). To divide these items into \(n\) different categories, we need \(n-1\) separators (the “bars,” |). The total number of ways to make the selection is equivalent to the number of ways we can arrange these \(k\) stars and \(n-1\) bars in a sequence.

We have a total of \(k + n - 1\) positions. We just need to choose which of these positions will be stars (the rest will be bars). Therefore, the formula is: \[ \binom{n+k-1}{k} \quad \text{or equivalently} \quad \binom{n+k-1}{n-1} \]

1.6 Binomial and Multinomial Theorems
1.6.1 The Binomial Theorem

The term \(\binom{n}{k}\) is also known as a binomial coefficient because it appears in the expansion of binomial powers like \((x+y)^n\).

The Binomial Theorem provides a formula for this expansion: \[ (x+y)^n = \sum_{j=0}^{n} \binom{n}{j} x^{n-j}y^j \] Combinatorial Proof: When expanding \((x+y)(x+y)\dots(x+y)\), each term in the result is formed by picking either an x or a y from each of the n factors. To form a term \(x^{n-j}y^j\), we must choose y from j of the factors and x from the remaining n-j factors. The number of ways to choose which j factors contribute a y is precisely \(\binom{n}{j}\).

1.6.2 The Multinomial Theorem

The Multinomial Theorem generalizes the Binomial Theorem to more than two variables, such as \((x_1 + x_2 + \dots + x_m)^n\). The coefficients in this expansion are called multinomial coefficients.

A multinomial coefficient counts the number of ways to arrange n objects when there are \(k_1\) indistinguishable objects of type 1, \(k_2\) of type 2, …, and \(k_m\) of type m, where \(k_1 + k_2 + \dots + k_m = n\). The formula is: \[ \binom{n}{k_1, k_2, \dots, k_m} = \frac{n!}{k_1!k_2!\dots k_m!} \] The full Multinomial Theorem is: \[ (x_1 + x_2 + \dots + x_m)^n = \sum_{k_1+k_2+\dots+k_m=n} \binom{n}{k_1, k_2, \dots, k_m} x_1^{k_1} x_2^{k_2} \dots x_m^{k_m} \]

2. Definitions

  • Combinatorics: The branch of mathematics dealing with the counting, arrangement, and combination of objects.
  • Sum Rule: A counting principle stating that if there are \(n_1\) ways for a first event to occur and \(n_2\) ways for a second, mutually exclusive event to occur, then there are \(n_1 + n_2\) ways for either event to occur.
  • Product Rule: A counting principle stating that if a procedure consists of two independent steps, with \(n_1\) ways to perform the first step and \(n_2\) ways to perform the second, there are \(n_1 \times n_2\) total ways to perform the procedure.
  • Permutation: An arrangement of objects in a specific order. The number of ordered arrangements of k distinct items from a set of n is denoted \(P(n, k)\).
  • Combination: A selection of objects where the order does not matter. The number of unordered subsets of k items from a set of n is denoted \(C(n, k)\) or \(\binom{n}{k}\).
  • Unordered Pair: A set of two elements {a, b} where the order is not considered; {a, b} is the same as {b, a}.
  • Ordered Pair: A pair of elements (a, b) where the order is significant; (a, b) is distinct from (b, a).
  • Binomial Coefficient: The number of ways to choose k elements from a set of n elements without regard to order, written as \(\binom{n}{k}\).
  • Multinomial Coefficient: A generalization of the binomial coefficient, used to find the number of ways to partition a set of n items into m groups of sizes \(k_1, k_2, \dots, k_m\).

3. Formulas

  • Ordered Arrangement with Repetition: \(n^k\)
  • Ordered Arrangement without Repetition (Permutation): \[P(n, k) = \frac{n!}{(n-k)!}\]
  • Permutation of n distinct items: \(n!\)
  • Unordered Arrangement without Repetition (Combination): \[C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\]
  • Permutations with Repetition (Multinomial Coefficient): \[\frac{n!}{n_1!n_2!\dots n_k!}\]
  • Coefficient of \(x^{j}y^{k}\) in \((ax+by)^n\): \[\binom{n}{k} a^{j} b^k\]
  • Unordered Arrangement with Repetition (Stars and Bars): \[C(n+k-1, k) = \binom{n+k-1}{k}\]
  • Solutions to \(x_1 + \dots + x_k = n\) for \(x_i \ge 0\): \[C(n+k-1, k-1) = \binom{n+k-1}{k-1}\]
  • Complementary Counting: \(|A| = |Total| - |\overline{A}|\)
  • Principle of Inclusion-Exclusion for Complements: \(|A \cap B| = |Total| - (|\overline{A}| + |\overline{B}| - |\overline{A} \cap \overline{B}|)\)

4. Examples

4.1. Calculate Word Formations (Lab 6, Task 1)

How many possible ways are there to form five-letter words using only the letters A-H? How many such words consist of five distinct letters?

Click to see the solution
  1. Part 1: Five-letter words (repetition allowed):
    • Analyze the problem: We are forming a sequence of 5 letters from a set of 8 (A through H), where repetition is allowed.
    • Apply the Product Rule: There are 5 positions in the word. For each position, there are 8 possible choices of letters.
    • Calculation: The total number of possible words is \(8 \times 8 \times 8 \times 8 \times 8 = 8^5\).
    • Result: \(8^5 = 32,768\).
  2. Part 2: Five-letter words with distinct letters (no repetition):
    • Analyze the problem: We are arranging 5 distinct letters chosen from a set of 8. This is a permutation.
    • Apply the Permutation Formula: The number of permutations of r items chosen from n is \(P(n, r) = \frac{n!}{(n-r)!}\).
    • Calculation: Here, n=8 and r=5. \(P(8, 5) = \frac{8!}{(8-5)!} = \frac{8!}{3!} = 8 \times 7 \times 6 \times 5 \times 4\).
    • Result: \(P(8, 5) = 6,720\).
Answer: There are 32,768 possible five-letter words, and 6,720 of them consist of distinct letters.
4.2. Calculate Number Plate Combinations (Lab 6, Task 2)

How many different number plates for cars can be made if each number plate contains two letters (A-Z) followed by five digits (0-9)?

Click to see the solution
  1. Analyze the structure: The plate format is Letter-Letter-Digit-Digit-Digit-Digit-Digit.
  2. Count the choices for each position:
    • Position 1 (Letter): 26 choices.
    • Position 2 (Letter): 26 choices.
    • Position 3 (Digit): 10 choices.
    • Position 4 (Digit): 10 choices.
    • Position 5 (Digit): 10 choices.
    • Position 6 (Digit): 10 choices.
    • Position 7 (Digit): 10 choices.
  3. Apply the Product Rule: Multiply the number of choices for each position to get the total number of unique plates.
    • Total = \(26 \times 26 \times 10 \times 10 \times 10 \times 10 \times 10 = 26^2 \times 10^5\).
  4. Calculate the result:
    • Total = \(676 \times 100,000 = 67,600,000\).
Answer: There can be 67,600,000 different number plates.
4.3. Calculate Flag Design Possibilities (Lab 6, Task 3)

We want to design a flag that consists of three horizontal stripes; the colour of the middle stripe should be different from the other two stripes. How many possibilities are there, if the colours red, green, blue, yellow, black and white can be used?

Click to see the solution
  1. Analyze the constraints: There are 3 stripes (Top, Middle, Bottom) and 6 available colors. The main constraint is that the middle stripe’s color cannot be the same as the top or bottom stripe’s color. The top and bottom stripes can be the same color.
  2. Count the choices systematically: It’s best to start with the most constrained position, which is the middle stripe.
    • Choices for the Middle stripe: There are 6 available colors.
    • Choices for the Top stripe: The color can be anything except the color chosen for the middle stripe. This leaves 5 choices.
    • Choices for the Bottom stripe: The color can be anything except the color chosen for the middle stripe. This also leaves 5 choices.
  3. Apply the Product Rule: Multiply the number of choices for each stripe.
    • Total possibilities = (Choices for Top) \(\times\) (Choices for Middle) \(\times\) (Choices for Bottom) = \(5 \times 6 \times 5 = 150\).
Answer: There are 150 possible flag designs.
4.4. Calculate the Diagonals of a Polygon (Lab 6, Task 4)

How many diagonals does a regular dodecagon (a twelve-sided polygon) have?

Click to see the solution
  1. Analyze the problem: A diagonal is a line segment that connects two non-adjacent vertices of a polygon.
  2. Count all possible lines: A dodecagon has 12 vertices. The total number of line segments that can be drawn between any two vertices is given by the combination formula \(C(n, 2)\), where n is the number of vertices.
    • Total lines = \(C(12, 2) = \frac{12!}{2!(10)!} = \frac{12 \times 11}{2} = 66\).
  3. Subtract the sides: The total number of lines calculated above includes the 12 sides of the dodecagon. The diagonals are all of these lines except for the sides.
    • Number of diagonals = (Total lines) - (Number of sides).
    • Number of diagonals = \(66 - 12 = 54\).
Answer: A regular dodecagon has 54 diagonals.
4.5. Calculate Committee Compositions (Lab 6, Task 5)

There are 15 mathematicians and 20 physicists at the faculty; how many possible committees of 8 members are there, if there must be more mathematicians than physicists (but at least one physicist) on the committee?

Click to see the solution
  1. Identify the constraints: The committee has 8 members. Let ‘m’ be the number of mathematicians and ‘p’ be the number of physicists.
    • \(m + p = 8\)
    • \(m > p\)
    • \(p \ge 1\)
  2. List the valid compositions (m, p):
    • If p=1, then m=7. (Valid, since 7 > 1)
    • If p=2, then m=6. (Valid, since 6 > 2)
    • If p=3, then m=5. (Valid, since 5 > 3)
    • If p=4, then m=4. (Invalid, since 4 is not > 4)
  3. Calculate the number of ways for each case:
    • Case 1 (7 mathematicians, 1 physicist): Choose 7 from 15 mathematicians AND 1 from 20 physicists.
      • \(C(15, 7) \times C(20, 1) = 6435 \times 20 = 128,700\).
    • Case 2 (6 mathematicians, 2 physicists): Choose 6 from 15 mathematicians AND 2 from 20 physicists.
      • \(C(15, 6) \times C(20, 2) = 5005 \times 190 = 950,950\).
    • Case 3 (5 mathematicians, 3 physicists): Choose 5 from 15 mathematicians AND 3 from 20 physicists.
      • \(C(15, 5) \times C(20, 3) = 3003 \times 1140 = 3,423,420\).
  4. Sum the results: The total number of possible committees is the sum of the possibilities from all valid cases.
    • Total = \(128,700 + 950,950 + 3,423,420 = 4,503,070\).
Answer: There are 4,503,070 possible committees.
4.6. Counting Palindromes (Lab 6, Task 6)

How many 9-letter palindromes (not necessarily meaningful) can be formed using the letters A-Z?

Click to see the solution
  1. Analyze the structure of a palindrome: A 9-letter palindrome is determined by its first 5 letters. The structure is \(L_1 L_2 L_3 L_4 L_5 L_4 L_3 L_2 L_1\).
  2. Count the independent choices: Once we choose the first five letters, the remaining four are automatically determined. We can choose any of the 26 letters for each of the first five positions, as repetition is allowed.
    • Choices for the 1st letter: 26 (determines the 9th letter).
    • Choices for the 2nd letter: 26 (determines the 8th letter).
    • Choices for the 3rd letter: 26 (determines the 7th letter).
    • Choices for the 4th letter: 26 (determines the 6th letter).
    • Choices for the 5th letter (the center): 26.
  3. Apply the Product Rule: The total number of possible palindromes is the product of the number of choices for the independent positions.
    • Total = \(26 \times 26 \times 26 \times 26 \times 26 = 26^5\).
  4. Calculate the result:
    • \(26^5 = 11,881,376\).
Answer: There are 11,881,376 possible 9-letter palindromes.
4.7. Counting Arrangements (Lab 6, Task 7)

The four women Anne, Betsie, Charlotte and Dolores and the six men Eric, Frank, George, Harry, Ian and James are friends. Each of the women wants to marry one of the six men. In how many ways can this be done?

Click to see the solution
  1. Analyze the problem: We are assigning a unique man to each of the four women. The order of assignment matters (e.g., Anne marrying Eric is different from Anne marrying Frank). This is a permutation problem where we are arranging 4 men selected from the 6 available.
  2. Apply the Permutation Formula: The number of permutations of r items chosen from n is \(P(n, r) = \frac{n!}{(n-r)!}\).
  3. Step-by-step assignment:
    • Anne has 6 choices of men.
    • Once Anne’s choice is made, Betsie has 5 remaining choices.
    • Charlotte then has 4 remaining choices.
    • Dolores has 3 remaining choices.
  4. Calculate the result:
    • Total ways = \(P(6, 4) = 6 \times 5 \times 4 \times 3 = 360\).
Answer: This can be done in 360 ways.
4.8. Counting Subsets (Lab 6, Task 8)

How many six-element subsets of {1, 2, 3, …, 10}? How many five-element subsets of {1, 2, 3, …, 10} contain at least one odd element?

Click to see the solution
  1. Part 1: Six-element subsets:
    • Analyze the problem: We are choosing 6 elements from a set of 10, and the order does not matter. This is a combination.
    • Apply the Combination Formula: \(C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\).
    • Calculation: \(C(10, 6) = \binom{10}{6} = \frac{10!}{6!4!} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210\).
  2. Part 2: Five-element subsets with at least one odd element:
    • Analyze the problem: It’s easier to calculate the total number of subsets and subtract the ones that do not meet the condition (the complementary event).
    • Total five-element subsets: \(C(10, 5) = \frac{10!}{5!5!} = 252\).
    • Subsets with no odd elements: The original set has 5 odd numbers {1,3,5,7,9} and 5 even numbers {2,4,6,8,10}. A subset with no odd elements must be composed entirely of even numbers. We need to choose 5 elements from the 5 available even numbers.
    • Calculation for complement: \(C(5, 5) = 1\). (The only such subset is {2,4,6,8,10}).
    • Final Calculation: (Total subsets) - (Subsets with only even numbers) = \(252 - 1 = 251\).
Answer: There are 210 six-element subsets. There are 251 five-element subsets that contain at least one odd element.
4.9. Using the Multinomial Theorem (Lab 6, Task 9.a)

Determine the coefficient of the term \(x^3y^4z\) in the expansion of \((x + y^2 + z)^6\).

Click to see the solution
  1. Analyze the problem: We need to find the term of the form \((x)^a(y^2)^b(z)^c\) where the final powers are \(x^3y^4z^1\).
  2. Match the powers:
    • For x, we need \(a = 3\).
    • For y, we need \(2b = 4\), which means \(b = 2\).
    • For z, we need \(c = 1\).
  3. Check the total power: The sum of the exponents in the multinomial expansion must equal n. Here, \(a+b+c = 3+2+1 = 6\), which matches the power of the expression.
  4. Apply the Multinomial Theorem: The coefficient for the term \((x)^3(y^2)^2(z)^1\) is given by the multinomial coefficient \(\binom{n}{a, b, c} = \frac{n!}{a!b!c!}\).
  5. Calculate the coefficient:
    • Coefficient = \(\frac{6!}{3!2!1!} = \frac{720}{6 \times 2 \times 1} = \frac{720}{12} = 60\).
Answer: The coefficient is 60.
4.10. Using the Multinomial Theorem (Lab 6, Task 9.b)

Determine the coefficient of the term \(x^3y^4z\) in the expansion of \((2x - y - 3z)^8\).

Click to see the solution
  1. Analyze the problem: We are expanding \(( (2x) + (-y) + (-3z) )^8\). We need the term where the powers of the variables are \(x^3y^4z^1\).
  2. Match the powers: The powers of the terms are \(a=3\) for (2x), \(b=4\) for (-y), and \(c=1\) for (-3z).
  3. Check the total power: \(a+b+c = 3+4+1 = 8\), which matches the power of the expression.
  4. Apply the Multinomial Theorem: The full term is given by \(\binom{n}{a, b, c} (2x)^a (-y)^b (-3z)^c\).
  5. Calculate the coefficient: The coefficient is the numerical part of this term: \(\binom{8}{3, 4, 1} \cdot (2)^3 \cdot (-1)^4 \cdot (-3)^1\).
    • \(\binom{8}{3, 4, 1} = \frac{8!}{3!4!1!} = \frac{40320}{6 \times 24 \times 1} = 280\).
    • \(2^3 = 8\).
    • \((-1)^4 = 1\).
    • \((-3)^1 = -3\).
    • Total coefficient = \(280 \times 8 \times 1 \times (-3) = -6720\).
Answer: The coefficient is -6,720.
4.11. Calculate Permutations with Repetition (Lab 6, Task 10)

In how many possible orders can the letters of the word MATHEMATICS be arranged? What if the two letters M shouldn’t stand together?

Click to see the solution
  1. Part 1: Total possible arrangements:
    • Analyze the word: “MATHEMATICS” has 11 letters.
    • Count repetitions: M (2), A (2), T (2), H (1), E (1), I (1), C (1), S (1).
    • Apply the formula for permutations with repetition: \(\frac{n!}{n_1!n_2!...} = \frac{11!}{2!2!2!} = \frac{39,916,800}{8} = 4,989,600\).
  2. Part 2: Arrangements where the two M’s are not together:
    • Use the complementary approach: (Total arrangements) - (Arrangements where the two M’s ARE together).
    • Calculate arrangements with M’s together: Treat “MM” as a single block. Now we are arranging the 10 items: (MM), A, T, H, E, I, C, S, A, T.
    • Count repetitions in this new set: A (2), T (2).
    • Calculate permutations for the blocked set: \(\frac{10!}{2!2!} = \frac{3,628,800}{4} = 907,200\).
    • Calculate the final result: \(4,989,600 - 907,200 = 4,082,400\).
Answer: There are 4,989,600 total arrangements. There are 4,082,400 arrangements where the two M’s are not together.
4.12. Counting Paths on a Grid (Lab 6, Task 11)

A single piece is placed on the lower-left corner square of an 8×8-chessboard. The piece may only move horizontally or vertically, one square at a time. How many possible ways are there to move the piece to the opposite corner in 14 moves (the smallest possible number of moves)?

Click to see the solution
  1. Analyze the problem: To get from the lower-left corner (let’s call it (0,0)) to the upper-right corner (7,7) on an 8x8 board, the piece must make 7 moves to the right (R) and 7 moves upwards (U).
  2. Smallest number of moves: The total number of moves must be \(7 + 7 = 14\). The problem states we are using 14 moves, so we are looking for the number of shortest paths.
  3. Frame as a permutation problem: Any sequence of 7 R’s and 7 U’s will result in a valid path. For example, RRRRRRRUUUUUUU or RURURURURURURU. The problem is equivalent to finding the number of distinct ways to arrange these 14 moves.
  4. Apply the formula for permutations with repetition: We have n=14 total moves, with \(n_1=7\) repetitions of ‘R’ and \(n_2=7\) repetitions of ‘U’.
    • Number of ways = \(\frac{14!}{7!7!}\).
  5. Calculate the result: This is the combination formula \(C(14, 7)\).
    • \(C(14, 7) = \frac{14 \times 13 \times 12 \times 11 \times 10 \times 9 \times 8}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = 3,432\).
Answer: There are 3,432 possible ways.
4.13. Counting Subsets with Conditions (Lab 6, Task 13)

How many 3-element subsets of {1, 2, 3, …, 100} contain at least one element that is divisible by 2 and at least one element that is divisible by 5?

Click to see the solution
  1. Use the Principle of Inclusion-Exclusion on the complement: It’s easier to find the total number of subsets and subtract the ones that don’t meet the condition.
    • Let A be the property “at least one element is divisible by 2”.
    • Let B be the property “at least one element is divisible by 5”. We want to find \(|A \cap B|\).
    • \(|A \cap B| = |Total| - |\overline{A} \cup \overline{B}| = |Total| - (|\overline{A}| + |\overline{B}| - |\overline{A} \cap \overline{B}|)\).
  2. Count the elements in the base set:
    • Total numbers: 100.
    • Divisible by 2 (Evens): 50. Not divisible by 2 (Odds): 50.
    • Divisible by 5: 20. Not divisible by 5: 80.
    • Not div by 2 AND not div by 5: These are odd numbers that don’t end in 5. There are 50 odd numbers, and 10 of them end in 5 ({5, 15, …, 95}). So there are \(50 - 10 = 40\) such numbers.
  3. Calculate the quantities:
    • \(|Total|\): Total 3-element subsets is \(C(100, 3) = 161,700\).
    • \(|\overline{A}|\): Subsets with NO elements divisible by 2 (all odd). We choose 3 from the 50 odd numbers: \(C(50, 3) = 19,600\).
    • \(|\overline{B}|\): Subsets with NO elements divisible by 5. We choose 3 from the 80 such numbers: \(C(80, 3) = 82,160\).
    • \(|\overline{A} \cap \overline{B}|\): Subsets with NO elements divisible by 2 or 5. We choose 3 from the 40 such numbers: \(C(40, 3) = 9,880\).
  4. Calculate the final result:
    • \(|\overline{A} \cup \overline{B}| = 19,600 + 82,160 - 9,880 = 91,880\).
    • \(|A \cap B| = 161,700 - 91,880 = 69,820\).
Answer: There are 69,820 such subsets.
4.14. Using Combinations with Repetition (Lab 6, Task 14)

There are 4 varieties of cakes in a cafe: chocolate, cream, nuts, jam. How many ways are there to order 7 cakes?

Click to see the solution
  1. Analyze the problem: This is a combination with repetition problem. We are choosing 7 items (the cakes) from 4 categories (the varieties). The order in which we choose the cakes does not matter, only the final count of each variety.
  2. Apply the “Stars and Bars” formula: The number of ways to choose k items from n categories with repetition is \(C(k+n-1, k)\).
  3. Identify n and k:
    • k = 7 (the number of cakes to choose).
    • n = 4 (the number of varieties).
  4. Calculate the result:
    • \(C(7+4-1, 7) = C(10, 7) = \binom{10}{7}\).
    • \(\binom{10}{7} = \binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120\).
Answer: There are 120 ways to order the 7 cakes.
4.15. Integer Solutions to an Equation (Lab 6, Task 15)

How many different solutions in non-negative integers \(x_1, x_2, x_3, x_4\) does the equation \(x_1 + x_2 + x_3 + x_4 = 8\) have? What if \(x_i \geq 1\)?

Click to see the solution
  1. Part 1: Non-negative integers (\(x_i \ge 0\)):
    • Analyze the problem: This is a standard “stars and bars” problem. We are distributing n=8 “stars” (units) into k=4 “bins” (variables).
    • Apply the formula: The number of solutions is \(C(n+k-1, k-1)\).
    • Calculation: \(C(8+4-1, 4-1) = C(11, 3) = \frac{11 \times 10 \times 9}{3 \times 2 \times 1} = 165\).
  2. Part 2: Positive integers (\(x_i \ge 1\)):
    • Analyze the problem: We can first give one unit to each of the four variables to satisfy the \(x_i \ge 1\) condition. This uses up 4 units.
    • Transform the equation: Let \(x_i = y_i + 1\), where \(y_i \ge 0\).
    • \((y_1+1) + (y_2+1) + (y_3+1) + (y_4+1) = 8\).
    • This simplifies to \(y_1 + y_2 + y_3 + y_4 = 4\).
    • Solve the new equation: Now we solve for the non-negative integers \(y_i\). This is another “stars and bars” problem with n=4 and k=4.
    • Calculation: \(C(4+4-1, 4-1) = C(7, 3) = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35\).
Answer: There are 165 non-negative integer solutions and 35 positive integer solutions.
4.16. Using the Product Rule (Tutorial 6, Task 1)

How many car number plates can be made if each plate contains 2 letters of the Latin alphabet, followed by 3 digits?

Click to see the solution
  1. Analyze the structure: A number plate has 5 positions in total: Letter, Letter, Digit, Digit, Digit.
  2. Count choices for each position:
    • Position 1 (Letter): There are 26 possible choices (A-Z).
    • Position 2 (Letter): There are 26 possible choices.
    • Position 3 (Digit): There are 10 possible choices (0-9).
    • Position 4 (Digit): There are 10 possible choices.
    • Position 5 (Digit): There are 10 possible choices.
  3. Apply the Product Rule: To find the total number of combinations, we multiply the number of choices for each position.
    • Total possibilities = \(26 \times 26 \times 10 \times 10 \times 10\).
  4. Calculate the result:
    • \(26^2 \times 10^3 = 676 \times 1000 = 676,000\).
Answer: It is possible to create 676,000 different number plates.
4.17. Using the Product Rule (Tutorial 6, Task 2)

Each user on a computer system has a password, which is 6 characters long, where each character is an uppercase letter (A-Z) or a digit (0-9). How many possible passwords are there?

Click to see the solution
  1. Analyze the structure: The password has 6 character positions.
  2. Count choices for each position:
    • For each of the 6 positions, a character can be an uppercase letter (26 options) or a digit (10 options).
    • Total choices per position = \(26 + 10 = 36\).
  3. Apply the Product Rule: Since each position is independent, we multiply the number of choices for each of the 6 positions.
    • Total possibilities = \(36 \times 36 \times 36 \times 36 \times 36 \times 36 = 36^6\).
  4. Calculate the result:
    • \(36^6 = 2,176,782,336\).
Answer: There are 2,176,782,336 possible passwords.
4.18. Using the Product Rule (Tutorial 6, Task 4)

How many words of length 5 can be made from the letters ABCDEFGH?

Click to see the solution
  1. Analyze the problem: We are creating a “word” of length 5 from a set of 8 distinct letters. Since the problem uses the term “word” and doesn’t specify otherwise, we assume that letters can be repeated.
  2. Count choices for each position: There are 5 positions in the word.
    • Position 1: 8 choices.
    • Position 2: 8 choices.
    • Position 3: 8 choices.
    • Position 4: 8 choices.
    • Position 5: 8 choices.
  3. Apply the Product Rule: Multiply the number of choices for each position.
    • Total possibilities = \(8 \times 8 \times 8 \times 8 \times 8 = 8^5\).
  4. Calculate the result:
    • \(8^5 = 32,768\).
Answer: There are 32,768 possible words.
4.19. Calculate Permutations (Tutorial 6, Task 5)

How many permutations of length 5 can be made from the letters ABCDEFGH?

Click to see the solution
  1. Analyze the problem: We are finding the number of permutations (arrangements where order matters and repetition is not allowed) of length 5 from a set of 8 distinct letters.
  2. Use the permutation formula: The number of permutations of r items chosen from a set of n distinct items is given by the formula \(P(n, r) = \frac{n!}{(n-r)!}\).
  3. Apply the formula:
    • Here, n = 8 (total letters) and r = 5 (length of the permutation).
    • \(P(8, 5) = \frac{8!}{(8-5)!} = \frac{8!}{3!}\).
  4. Calculate the result:
    • \(P(8, 5) = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 8 \times 7 \times 6 \times 5 \times 4 = 6,720\).
Answer: There are 6,720 possible permutations.
4.20. Calculate Permutations with a Substring (Tutorial 6, Task 6)

How many permutations of the letters ABCDEFGH contain the string ABC as a (consecutive) substring?

Click to see the solution
  1. Treat the substring as a single block: To ensure the letters ABC appear consecutively and in that order, we can treat the block “ABC” as a single, indivisible unit.
  2. Identify the items to be permuted: The new set of items to arrange is {(ABC), D, E, F, G, H}.
  3. Count the items: We now have 6 distinct items to permute.
  4. Calculate the number of permutations: The number of ways to arrange n distinct items is n!.
    • Number of permutations = \(6!\).
  5. Calculate the result:
    • \(6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\).
Answer: There are 720 permutations that contain the substring ABC.
4.21. Calculate Combinations (Tutorial 6, Task 7)

We need to create a team of 5 players for the competition out of 10 team members. How many different teams is it possible to create?

Click to see the solution
  1. Analyze the problem: We are selecting a group of 5 players from a larger group of 10. Since the order in which the players are chosen for the team does not matter, this is a combination problem.
  2. Use the combination formula: The number of combinations of r items chosen from a set of n items is given by \(C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}\).
  3. Apply the formula:
    • Here, n = 10 (total members) and r = 5 (team size).
    • \(C(10, 5) = \binom{10}{5} = \frac{10!}{5!(10-5)!} = \frac{10!}{5!5!}\).
  4. Calculate the result:
    • \(C(10, 5) = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 2 \times 3 \times 2 \times 7 \times 3 = 252\).
Answer: It is possible to create 252 different teams.
4.22. Calculate Partitions (Tutorial 6, Task 8)

We need to create 3 teams of 5 players for the competition out of 15 students. How many different ways is it possible to create the teams?

Click to see the solution
  1. Analyze the problem: We are partitioning a set of 15 students into 3 unordered groups of 5.
  2. Step-by-step selection:
    • First, choose 5 students for the first team from 15: \(C(15, 5)\).
    • Next, choose 5 students for the second team from the remaining 10: \(C(10, 5)\).
    • Finally, choose 5 students for the third team from the remaining 5: \(C(5, 5)\).
  3. Account for indistinguishable teams: The problem asks for “3 teams,” not “Team A, Team B, and Team C.” Since the teams are not labeled, the order in which we form them does not matter. There are \(3!\) ways to order the three teams, so we must divide by \(3!\) to avoid overcounting.
  4. Set up the calculation:
    • Total ways = \(\frac{C(15, 5) \times C(10, 5) \times C(5, 5)}{3!}\).
    • \(C(15, 5) = \frac{15!}{5!10!} = 3003\).
    • \(C(10, 5) = \frac{10!}{5!5!} = 252\).
    • \(C(5, 5) = 1\).
  5. Calculate the final result:
    • Total ways = \(\frac{3003 \times 252 \times 1}{3 \times 2 \times 1} = \frac{756756}{6} = 126,126\).
Answer: It is possible to create 126,126 different sets of teams.
4.23. Calculate Permutations with Repetition (Tutorial 6, Task 9)

How many different strings can be made by reordering the letters of the word “SUCCESS”?

Click to see the solution
  1. Analyze the word: The word “SUCCESS” has 7 letters in total.
  2. Count the repetitions:
    • The letter ‘S’ appears 3 times.
    • The letter ‘C’ appears 2 times.
    • The letters ‘U’ and ‘E’ each appear 1 time.
  3. Use the formula for permutations with repetition: The number of distinct permutations of n objects where there are \(n_1\) identical objects of type 1, \(n_2\) of type 2, …, and \(n_k\) of type k is \(\frac{n!}{n_1! n_2! \dots n_k!}\).
  4. Apply the formula:
    • \(n = 7\), \(n_1 = 3\) (for S), \(n_2 = 2\) (for C).
    • Number of strings = \(\frac{7!}{3!2!}\).
  5. Calculate the result:
    • \(\frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(2 \times 1)} = \frac{5040}{12} = 420\).
Answer: There are 420 different strings that can be made.
4.24. Using the Binomial Theorem (Tutorial 6, Task 10)

What is the coefficient of the term \(x^8y^6\) in the expansion of \((2x + 3y)^{14}\)?

Click to see the solution
  1. Recall the Binomial Theorem: The term containing \(a^{n-k}b^k\) in the expansion of \((a+b)^n\) is given by \(\binom{n}{k} a^{n-k} b^k\).
  2. Identify the components:
    • \(a = 2x\), \(b = 3y\), \(n = 14\).
    • We are looking for the term with \(x^8y^6\). This means \((2x)^8\) and \((3y)^6\).
    • So, \(n-k = 8\) and \(k=6\). This is consistent since \(8+6=14=n\).
  3. Construct the term: The full term is \(\binom{14}{6} (2x)^8 (3y)^6\).
  4. Calculate the coefficient: We need to evaluate the numerical part of the term: \(\binom{14}{6} \cdot 2^8 \cdot 3^6\).
    • \(\binom{14}{6} = \frac{14!}{6!8!} = 3003\).
    • \(2^8 = 256\).
    • \(3^6 = 729\).
  5. Multiply the parts:
    • Coefficient = \(3003 \times 256 \times 729 = 560,013,552\).
Answer: The coefficient is 560,013,552.
4.25. Using the Multinomial Theorem (Tutorial 6, Task 11)

What is the coefficient of the term \(x^2y^3z^2\) in the expansion of \((x + y + z)^7\)?

Click to see the solution
  1. Recall the Multinomial Theorem: The coefficient of the term \(x_1^{n_1} x_2^{n_2} \dots x_k^{n_k}\) in the expansion of \((x_1 + x_2 + \dots + x_k)^n\) is given by the multinomial coefficient \(\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \dots n_k!}\).
  2. Identify the components:
    • \(n=7\).
    • We want the term \(x^2y^3z^2\), so the powers are \(n_1=2\), \(n_2=3\), and \(n_3=2\). (Note that \(2+3+2=7=n\)).
  3. Apply the formula: The coefficient is \(\binom{7}{2, 3, 2} = \frac{7!}{2!3!2!}\).
  4. Calculate the result:
    • \(\frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(2 \times 1)(3 \times 2 \times 1)(2 \times 1)} = \frac{5040}{2 \times 6 \times 2} = \frac{5040}{24} = 210\).
Answer: The coefficient is 210.
4.26. Using the Multinomial Theorem (Tutorial 6, Task 12)

What is the coefficient of the term \(x^3y^4z^3\) in the expansion of \((x + 2y - z)^{10}\)?

Click to see the solution
  1. Identify the components: The expansion is of \((x + (2y) + (-z))^{10}\).
    • \(n=10\).
    • The powers for the variables are \(x^3\), \(y^4\), and \(z^3\). So, \(n_1=3\), \(n_2=4\), and \(n_3=3\). (Note that \(3+4+3=10=n\)).
  2. Construct the term using the Multinomial Theorem: The full term is \(\binom{10}{3, 4, 3} (x)^3 (2y)^4 (-z)^3\).
  3. Isolate the coefficient: The numerical coefficient is \(\binom{10}{3, 4, 3} \cdot 1^3 \cdot 2^4 \cdot (-1)^3\).
  4. Calculate each part:
    • \(\binom{10}{3, 4, 3} = \frac{10!}{3!4!3!} = \frac{3,628,800}{6 \times 24 \times 6} = 4200\).
    • \(2^4 = 16\).
    • \((-1)^3 = -1\).
  5. Multiply the parts:
    • Coefficient = \(4200 \times 16 \times (-1) = -67,200\).
Answer: The coefficient is -67,200.
4.27. Using Combinations with Repetition (Tutorial 6, Task 13)

How many different ways are there to place 12 colored balls in a bag, when each ball should be either Red, Green, or Blue?

Click to see the solution
  1. Analyze the problem: This is a problem of combinations with repetition. We are choosing 12 items (the balls) from 3 categories (the colors), where the order of selection does not matter. The balls are distinguishable only by their color. This is equivalent to finding the number of groups of 12 items chosen from 3 types.
  2. Use the combinations with repetition formula: The number of ways to choose k items from n categories with repetition allowed is given by the formula \(C(n+k-1, k) = \binom{n+k-1}{k}\) or equivalently \(C(n+k-1, n-1) = \binom{n+k-1}{n-1}\).
  3. Identify n and k:
    • \(n = 3\) (number of categories/colors).
    • \(k = 12\) (number of items to choose/balls).
  4. Apply the formula:
    • \(C(3+12-1, 12) = C(14, 12) = \binom{14}{12}\).
    • This is equivalent to \(\binom{14}{14-12} = \binom{14}{2}\).
  5. Calculate the result:
    • \(\binom{14}{2} = \frac{14!}{2!(12)!} = \frac{14 \times 13}{2 \times 1} = 91\).
Answer: There are 91 different ways to compose the bag of 12 balls.
4.28. Using Combinations with Repetition (Tutorial 6, Task 14)

How many different solutions in non-negative integers \(x_1, x_2, and x_3\) does the equation \(x_1 + x_2 + x_3 = 11\) have?

Click to see the solution
  1. Analyze the problem: This is a classic “stars and bars” problem, which is a type of combination with repetition. We are distributing 11 “units” (stars) into 3 distinct “bins” (the variables \(x_1, x_2, x_3\)).
  2. Use the combinations with repetition formula: The number of non-negative integer solutions to an equation of this form is given by \(C(n+k-1, k-1) = \binom{n+k-1}{k-1}\).
  3. Identify n and k:
    • \(n = 11\) (the sum, or “stars”).
    • \(k = 3\) (the number of variables, or “bins”).
  4. Apply the formula:
    • \(C(11+3-1, 3-1) = C(13, 2) = \binom{13}{2}\).
  5. Calculate the result:
    • \(\binom{13}{2} = \frac{13!}{2!(11)!} = \frac{13 \times 12}{2 \times 1} = 78\).
Answer: There are 78 different solutions.